The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
An Autonomous System (AS) is a network or group of networks under common administration and with common routing policies. A typical example of autonomous system is a network administered and maintained by an Internet Service Provider (ISP). Customer networks, such as universities or corporations, connect to the ISP, and the ISP routes the network traffic originating from the customer networks to network destinations that may be in the same ISP or may be reachable only through other ISPs.
Usually, an autonomous system comprises network elements that are established on the edge of the system, and that serve as the system's ingress and egress points for network traffic. These network elements often, but not always, are routers and are referred to as Provider Edge (PE) network elements or as Autonomous System Border Routers (ASBRs). An autonomous system may also include other network elements that are not used as ingress or egress points for network traffic, and these network elements are referred to as provider network elements. Similarly, a customer network may comprise network elements that are established on the edge of the network, and that are referred to as Customer Edge (CE) network elements.
In order to facilitate the routing of network traffic through one or more autonomous systems, the network elements of the autonomous systems need to exchange routing information to various network destinations.
Border Gateway Protocol (BGP) is an exterior gateway protocol (EGP) that is used to exchange routing information among network elements (usually routers) in the same or different autonomous systems. A computer host that executes a BGP process is typically referred to as a BGP host or a BGP device. In order to exchange BGP routing information, two BGP hosts, or peers, first establish a transport protocol connection with one another. Initially, the BGP peers exchange messages to open a BGP session, and, after the BGP session is open, the BGP peers exchange their entire routing information. Thereafter, only updates or changes to the routing information are exchanged, or advertised, between the BGP peers. The exchanged routing information is maintained by the BGP peers during the existence of the BGP session.
The BGP routing information includes the complete route to each network destination that is reachable from a BGP host. A route comprises an address destination, which is usually represented by an address prefix (also referred to as prefix), and information that describe the path to the address destination. The address prefix may be expressed as a combination of a network address and a mask that indicates how many bits of the address are used to identify the network portion of the address. In Internet Protocol version 4 (IPv4) addressing, for example, the address prefix can be expressed as “9.2.0.2/16”. The “/16” indicates that the first 16 bits are used to identify the unique network leaving the remaining bits in the address to identify the specific hosts within this network.
In another example, Virtual Private Network (VPN) addressing schemes may use a route distinguisher (RD) in addition to the address prefix in order to distinguish between different routes to the same address destination. For example, in a VPN address destination of “10:9.2.0.2/16”, “10” is a route distinguisher that identifies a specific VPN route to the “9.2.0.2/16” network.
The information that describes the path to the address destination in a BGP route includes, but is not limited to, an ORIGIN attribute, an AS_PATH attribute, and a NEXT_HOP attribute. The ORIGIN attribute indicates how a BGP process learned about a particular route. The value of the ORIGIN attribute for a particular route may indicate that the route was learned from an Interior Gateway Protocol (IGP), from an EGP, such as external BGP (eBGP), or that the origin of the route is unknown or learned in some other way.
The AS_PATH attribute indicates the list of autonomous systems that must be traversed in order to reach the address destination. For example, an AS_PATH attribute of “130 120” for a route indicates that the route to the address destination passes through autonomous systems 120 and 130 in that order.
The NEXT_HOP attribute for a particular route contains the address of a network element that is the next hop to the address destination. For example, the NEXT_HOP attribute for a route that is received from an eBGP peer is the network address of the eBGP peer. In another example, a PE BGP host that advertises a VPN route will include its own network address as the NEXT_HOP attribute for the VPN route it advertises.
BGP peers exchange, or advertise, routes in BGP UPDATE messages. Under the BGP-4 standard described in RFC1771, which was published by the Internet Engineering Task Force (IETF) in March 1995 and which defines the mechanism for exchanging IPv4 routes, a BGP UPDATE message includes a message header, and some or all of the following fields:
(1) Unfeasible Routes Length—the length of the Withdrawn Routes field;
(2) Withdrawn Routes—the address prefixes of the routes being withdrawn from service;
(3) Total Path Attribute Length—the length of the Path Attribute field;
(4) Path Attributes—the attributes of the routes advertised in the BGP UPDATE message including, but not limited to, the NEXT_HOP attribute, the ORIGIN attribute, and the AS_PATH attribute;
(5) Network Layer Reachability Information (NLRI)—the address prefixes of feasible routes being advertised in the BGP UPDATE message.
In BGP-4, feasible, or reachable, routes are advertised between BGP peers in a BGP UPDATE message. The BGP UPDATE message carries the address prefixes of the routes in the NLRI field of the message. The different attributes of the routes, such as the ORIGIN, NEXT_HOP, and AS_PATH attributes are carried in the Path Attribute field of the BGP UPDATE message. All routes advertised in the same BGP UPDATE message share the same path attributes.
When a BGP host determines that a particular address destination is unavailable for whatever reason, the BGP host must withdraw all routes it has advertised as reachable through this unavailable address destination. The BGP host withdraws the routes by sending a BGP UPDATE message to its BGP peers. The BGP UPDATE message includes all the address prefixes of the routes being withdrawn in the Withdrawn Routes field as <length,prefix> tuples, where <length> is the length in bits of the associated <prefix>. The Unfeasible Routes Length field of the BGP UPDATE message includes the total length of the Withdrawn Routes field. The Path Attributes field and the NLRI field are blank or not included in the message. Thus, under the BGP-4 standard, in order to withdraw the unfeasible routes, a BGP host must include in the BGP UPDATE message all of the prefixes of the routes being withdrawn.
The same mechanism for withdrawing unfeasible routes is used in the Multiprotocol Extensions to BGP-4 (MP-BGP) protocol, which enables BGP-4 to carry routing information for multiple Network Layer protocols (e.g., Internet Protocol version 6 (IPv6), Internetwork Packet eXchange (IPX), VPN-IPv4, VPN-IPv6, etc.) MP-BGP is described in RFC2858, which was published by IETF in June 2000.
Specifically, MP-BGP provides a special path attribute, MP_UNREACH_NLRI, which includes a Withdrawn Routes field that stores the address prefixes of the withdrawn routes in <length,prefix> tuples. The MP_UNREACH_NLRI path attribute also includes an Address Family Identifier (AFI) field for storing the identify of the Network Layer protocol of the withdrawn routes, and a Subsequent Address Family Identifier (SAFI) field for storing additional information about the type of the Network Layer Reachability Information carried in the attribute. Most significantly, however, regardless of the address family of the routes being withdrawn (e.g. IPv6, IPX, VPN-IPv4, VPN-IPv6, etc.), the MP-BGP UPDATE message must include the address prefixes of all routes being withdrawn.
One disadvantage of this mechanism of withdrawing unfeasible routes is that it is not practical for large-scale use. For example, if a BGP host in an AS detects that a PE router in a neighboring AS has failed, the BGP host must withdraw every route that was reachable through the failed PE. Since the failed PE router may have provided reachability for thousands if not tens of thousands of routes, depending on the number of unique path attributes among all routes the BGP host may have to generate and transmit through the AS network a large number of BGP UPDATE messages that advertise separately the address prefixes associated with the each unique set of path attributes. The effect of transmitting a large number of BGP UPDATE messages will likely be decreased network bandwidth and will likely result in severe network traffic congestions. The network performance will further be degraded because every BGP peer that also forwards traffic will be slowed down since it must process the BGP UPDATE messages by reading and withdrawing from its routing tables every address prefix sent in the messages.
Furthermore, since a particular AS may have multiple BGP hosts and may provide transit network traffic services to other ASs, the multiple BGP hosts should have consistent information in their routing tables. Usually, the multiple BGP hosts in the AS use a common set of policies to arrive at an agreement as to which BGP hosts will serve as ingress and egress points for particular routes to other networks or ASs. It is desirable that this process, also known as BGP route convergence, takes as little time as possible in order to provide faster transit traffic services to other ASs.
However, if a large number of routes must be withdrawn, the existing route withdrawal mechanism in BGP will slow down the rate of convergence of routing information among the multiple BGP hosts in the AS. Since each BGP host must process a large number of BGP UPDATE messages and must identify and withdraw each route based on the address prefix of the route, it may take a long while before the BGP hosts can synchronize their routing tables and the routing information included therein.
Based on the foregoing, there is a clear need for techniques that overcome the disadvantages of the BGP route withdrawal mechanism described above.